package mo.tags.binarysearchtree;

import java.util.HashMap;
import java.util.Map;

public class L96 {

    private Map<Integer, Integer> cache = new HashMap<>();

    public int numTrees(int n) {
        if (n == 0 || n ==1) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int left = numTrees(i - 1);
            int right = numTrees(n-i);
            res += left * right;
        }
        cache.put(n, res);
        return res;
    }

}
